def Shell(List):
    # 初始步长
    step = len(List) // 2
    while step > 0:
        # 按步长进行插入排序
        for i in range(step, len(List)):
            j = i
            current = List[i]
            # 插入排序
            while j >= step and List[j - step] > current:
                List[j] = List[j - step]
                j = j - step
            List[j] = current
        # 新的步长
        step = step // 2
    return List


bef_list = [2, 78, 65, 4, 6, 2, 1, 7, 9, 4, 7, 8]
print(Shell(bef_list))
